package dp.integerBreak;
/**
 * @Date 2020/04/18
 * @author 王光浩
 * @Thinking 使用递归
 * @Analysis 时间复杂度O（2^n），空间复杂度O（n）
 */
public class MyMethodOne {
	public int integerBreak(int n) {
		int max = Integer.MIN_VALUE;
		for(int i=1 ; i<n ; i++)
			max = Math.max(max, helper(i,n-i) );
		return max;
    }
	private int helper(int value,int rest) {
		if( rest<=1 )return value;
		int max = Integer.MIN_VALUE;
		for(int i=1 ; i<=rest ; i++) {
			max = Math.max(max, value*helper(i,rest-i));
		}
		return max;
	}
}
